package leetcode_day._2021._202107._1120;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/14 21:33
 * 绝对差值和
 * 算法：二分查找
 * 找到 nums1 中能够替换的数
 * nums 由 nums1 克隆而来，再排序 nums
 * 在计算 nums1 和 nuns2 绝对差值和时，在 nums 中找到与 nums2 中相差最小的
 */
public class _14_1818 {
    public static void main(String[] args) {
        int a = 1 + 1 << 1;
        System.out.println(a);
    }

    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length, mod = (int) 1e9 + 7;
        int[] sorted = nums1.clone();
        Arrays.sort(sorted);
        long sum = 0, max = 0;
        for (int i = 0; i < n; i++) {
            int a = nums1[i], b = nums2[i];
            if (a == b) continue;
            int x = Math.abs(a - b);
            sum += x;
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (sorted[mid] <= b) l = mid;
                else r = mid - 1;
            }
            int nd = Math.abs(sorted[r] - b);
            if (r + 1 < n) nd = Math.min(nd, Math.abs(sorted[r + 1] - b));
            if (nd < x) max = Math.max(max, x - nd);
        }
        return (int)((sum - max) % mod);
    }

}
